Search for: All records

Abstract Extending a result of Christiansen, we prove that every multigraph admits a proper edge colouring which islocal, that is, for every edge with end‐points , where (resp. ) denotes the degree of a vertex (resp. the maximum edge multiplicity at ). This is derived from a local version of the Fan Equation. 

A long-standing open problem in the theory of hyperfinite equivalence relations asks if the orbit equivalence relation generated by a Borel action of a countable amenable group is hyperfinite. In this paper we prove that this question always has a positive answer when the acting group is polycyclic, and we obtain a positive answer for all free actions of a large class of solvable groups including the Baumslag–Solitar group BS(1, 2) and the lamplighter group Z2 ≀ Z. This marks the first time that a group of exponential volume-growth has been verified to have this property. In obtaining this result we introduce a new tool for studying Borel equivalence relations by extending Gromov’s notion of asymptotic dimension to the Borel setting. We show that countable Borel equivalence relations of finite Borel asymptotic dimension are hyperfinite, and more generally we prove under a mild compatibility assumption that increasing unions of such equivalence relations are hyperfinite. As part of our main theorem, we prove for a large class of solvable groups that all of their free Borel actions have finite Borel asymptotic dimension (and finite dynamic asymptotic dimension in the case of a continuous action on a zero dimensional space). We also provide applications to Borel chromatic numbers, Borel and continuous Følner tilings, topological dynamics, and C∗-algebras. 

Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit. 

An abstract system of congruences describes a way of partitioning a space into finitely many pieces satisfying certain congruence relations. Examples of abstract systems of congruences include paradoxical decompositions and $$n$$ -divisibility of actions. We consider the general question of when there are realizations of abstract systems of congruences satisfying various measurability constraints. We completely characterize which abstract systems of congruences can be realized by nonmeager Baire measurable pieces of the sphere under the action of rotations on the $$2$$ -sphere. This answers a question by Wagon. We also construct Borel realizations of abstract systems of congruences for the action of $$\mathsf{PSL}_{2}(\mathbb{Z})$$ on $$\mathsf{P}^{1}(\mathbb{R})$$ . The combinatorial underpinnings of our proof are certain types of decomposition of Borel graphs into paths. We also use these decompositions to obtain some results about measurable unfriendly colorings.